import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-02
 * Time: 18:43
 */
public class GraphByList {
    static class Node{
        private int src; // 起始位置
        private int dest; // 目标位置
        private int weight; //权
        private Node next;

        public Node(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }
    public char[] arrV;
    public ArrayList<Node> edgList; // 存储边
    public boolean isDirect;

    public GraphByList(int size, boolean isDirect){
        this.arrV = new char[size];
        this.isDirect = isDirect;
        this.edgList = new ArrayList<>(size);
        for (int i = 0; i < size; i++){
            edgList.add(null);
        }
    }
    /**
     * 顶点数组初始化
     */
    public void initArrV (char[] arrV){
        for (int i = 0; i < arrV.length; i++) {
            this.arrV[i] = arrV[i];
        }
    }

    /**
     * 添加边
     * @param srcV 开始顶点
     * @param destV 指向顶点
     * @param weight 权
     */
    public void addEdge(char srcV, char destV, int weight){
        int srcIndex = getIndexOfV(srcV);
        int destIndex = getIndexOfV(destV);
        if (srcIndex == -1) {
            System.out.println("没有顶点：" + srcV);
            return;
        }
        else if (destIndex == -1) {
            System.out.println("没有顶点：" + srcV);
            return;
        }
        addEdgeChild(srcIndex, destIndex,weight);
        //如果是无向图还需要添加：
        if (!isDirect) {
            addEdgeChild(destIndex, srcIndex, weight);
        }
    }


    private void addEdgeChild(int srcIndex, int destIndex, int weight){
        //判断是否已经存过了这条边
        Node cur = edgList.get(srcIndex);
        while (cur != null) {
            if (cur.dest == destIndex) return;
            cur = cur.next;
        }
        //没有存过，开始存，这里使用头插法
        Node node = new Node(srcIndex, destIndex, weight);
        node.next = edgList.get(srcIndex);
        edgList.set(srcIndex, node);
    }
    /**
     * 计算顶点的度
     * @param v 顶点
     * @return 度数
     */
    public int getDevOfV(char v){
        int vIndex = getIndexOfV(v);
        if (vIndex == -1) {
            System.out.println("没有顶点：" + v);
            return -1;
        }
        int count = 0;
        Node cur = edgList.get(vIndex);
        //计算出度
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        //如果是有向图还要计算入度
        if (isDirect) {
            for (int i = 0; i < arrV.length; i++) {
                if (i != vIndex){
                    cur = edgList.get(i);
                    while (cur != null) {
                        if (cur.dest == vIndex) count++;
                        cur = cur.next;
                    }
                }
            }
        }
        return count;
    }
    /**
     * 获取v下标
     */
    public int getIndexOfV(char v){
        for (int i = 0; i < this.arrV.length; i++){
            if (v == arrV[i]) return i;
        }
        return -1;
    }
    /**
     * 打印邻接表
     */
    public void printGraph(){
        for (int i = 0; i < arrV.length; i++){
            Node cur = edgList.get(i);
            while(cur != null){
                System.out.print(arrV[cur.src] + "->" + arrV[cur.dest] + " 权重为" + cur.weight + "; ");
                cur = cur.next;
            }
            System.out.println();
        }
    }
}
